1. Field of the Invention
This invention relates to a digital arithmetic circuit and more particularly to such a circuit having error detection properties.
2. Discussion of Prior Art
Digital arithmetic circuits are widely used in many fields of activity. Electronic technology has progressed rapidly over the past decade, and integrated circuit and system technology has increased in complexity as a result. Increasing complexity presents a number of problems, but in particular it results in reduced reliability due to ageing, transient malfunctions in operation and production faults during manufacture. These problems increase as circuit and system complexity increases and device size continues to decrease. A further aspect of increasing circuit complexity is that it may not be economically possible to fully test all aspects of a complex circuit or system. Such a circuit or system may therefore be produced in a form giving rise to unidentified errors. Detecting circuit errors becomes increasingly important for safety-critical applications, such as aircraft systems.
Methods of detecting errors are known, such as those employing Hamming codes as described in "Error Detecting and Error Correcting Codes", R W Hamming, Dell Systems Technical Journal, Vol 29 No 1 pp 147-160, January 1950. Hamming codes are parity check codes useful for checking data transmissions and storage. However, they have the important disadvantage that they are not preserved by arithmetic operations and cannot be used in arithmetic circuits.
Codes which overcome the limitation regarding preservation in arithmetic operations are described in "Error Detecting Code, Self-Checking Circuits and Applications", J Wakerly, Elsevier, North Holland Inc, 1978. A simple example is the so-called AN code. Here, input data words are multiplied by an applied multiplicand. Outputs which are not a multiple of the multiplicand can therefore be construed as containing errors.
Arithmetic codes all require additional circuitry to carry out initial coding and error checking. Additionally, more hardware is needed to implement the arithmetic function because coded data words are longer than uncoded ones.
Time redundant approaches to error detection have also been implemented. These methods require extra processing time compared with that normally required to perform the desired operation. Consequently, an operation which could be completed in one time unit without error detection might take two time units or more if carried out in an error detecting system employing time redundancy. An example of time redundancy has been suggested by Patel and Fung ("Concurrent Error Detection in ALU's by Recomputing with Shifted Operands", J H Patel and L Y Fung, IEEE Trans. on Computers, Vol C-31, pp 589-595, July 1982). This involves calculating a given result twice whilst shifting the position of the bits of the operands between the first and second calculation. After realigning the two output results, any error introduced by the hardware will appear in a different position in the two output values, and will be detectable. This approach is applicable to circuits such as arithmetic logic units (ALUs) which are constructed in a modular fashion with little or no connectivity between modules. This has the disadvantage that extra hardware modules are needed to handle the shifted operand.
The method of T H Chen et al ("Design of Concurrent Error-Detectable VLSI-Based Array Dividers", T H Chen, L G Chen, Y S Chang, Proc IEEE International Conference on Computer Design (ICCD), 1992) exploits circuit regularity to separate a circuit into two identical parts, each of which performs only half of the required calculation. Each part of the circuit is then used twice to generate two complete results which should be identical in the absence of errors. However, this approach is limited to circuits have regularity which enables separation for performing functions of calculations.
An adding and subtracting system is described in "Patent Abstracts of Japan", Volume 13 Number 460 (P-946), 18 Oct., 1989 which adds the result of the operations (A-B) and (B-A) and a zero check is then performed on this result.